//给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
//
// 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,0,2,1,1,0]
//输出：[0,0,1,1,2,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,0,1]
//输出：[0,1,2]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：[0]
// 
//
// 示例 4： 
//
// 
//输入：nums = [1]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 300 
// nums[i] 为 0、1 或 2 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以不使用代码库中的排序函数来解决这道题吗？ 
// 你能想出一个仅使用常数空间的一趟扫描算法吗？ 
// 
// Related Topics 数组 双指针 排序 
// 👍 1079 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class SortColors {
    public static void main(String[] args) {
        int[] nums = {1,2,0};
        new SortColors().new Solution().twoPointer(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * nums中元素个数只有三种 0 1 2
         * 选择一种排序方法实现（快速排序时间上肯定是比较能打的，空间稍微逊色）
         */
        public void sortColors(int[] nums) {
            //Arrays.sort(nums);
            quickSort(nums, 0, nums.length-1);
        }

        public void quickSort(int[] nums ,int left, int right){
            int l = left;
            int r = right;
            int pivot = nums[l + (r-l)/2];
            int temp = 0;
            while (l < r){
                while (nums[l]<pivot) l++;
                while (nums[r]>pivot) r--;
                if (l == r) break;
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                if (nums[l] == pivot) r--;
                if (nums[r] == pivot) l++;
             }
            if (l == r) {
                l++;
                r--;
            }
            if (left<r) quickSort(nums, left, r);
            if (right>l) quickSort(nums, l, right);
        }

        /**
         * 题解：双指针，一个从头部开始，一个从尾部开始，将整个数组分为三部分
         * [0,zero]存放0，[zero+1,two-1]存放1,[two,len-1]存放2
         */
        public void twoPointer(int[] nums){
            int len = nums.length;
            if (len<2) return;
            // 这样初始化是担心nums[0] nums[n-1]会以错误的值结束。
            // 然而只要数组里面有至少一个0和至少一个2， 它们肯定就会被放到0和n-1位置去
            // 所以初始化的时候可以直接设置为0和len-1
            int zero = -1;
            int two = len;
            int i = 0;
            while (i<two){
                // 这里交换后i要加1的原因是：交换回来的值只可能是0或1，对最终结果没有影响
                if (nums[i] == 0) swap(nums, ++zero, i++);
                else if (nums[i] == 1) i++;
                //TODO 注意这里交换完之后不知道交换回来的值是多少，所以i不能发生变化
                else swap(nums, --two, i);
            }
        }
        public void swap(int[] nums, int index1, int index2){
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}